package solutions.leetcode.normal;

import solutions.lib.BaseSolution;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/implement-trie-prefix-tree/">208. 实现 Trie (前缀树)</a>
 */
public class Solution208 extends BaseSolution {

    class Trie {
        Trie[] nexts;
        boolean isEnd;

        public Trie() {
            nexts = new Trie[26];
            isEnd = false;
        }

        public void insert(String word) {
            Trie node = this;
            for (int i = 0, len = word.length(); i < len; i++) {
                char c = word.charAt(i);
                if (node.nexts[c - 'a'] == null) {
                    node.nexts[c - 'a'] = new Trie();
                }
                node = node.nexts[c - 'a'];
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            Trie end = findEnd(word);
            return end != null && end.isEnd;
        }

        private Trie findEnd(String word) {
            Trie node = this;

            for (int i = 0, len = word.length(); i < len; i++) {
                char c = word.charAt(i);
                if (node.nexts[c - 'a'] == null) {
                    return null;
                }
                node = node.nexts[c - 'a'];
            }
            return node;
        }

        public boolean startsWith(String prefix) {
            Trie end = findEnd(prefix);
            return end != null;
        }
    }

    public static void main(String[] args) {
        Solution208 solution = new Solution208();
    }
}